public class Leetcode393 {

    public static void main(String[] args) {

    }

    private static final int HEIGHT_NUMBER = 7;

    private static final int MAX_BIT_NUMBER = 4;

    public boolean validUtf8(int[] data) {
        int n = data.length;
        for (int i = 0; i < n; ) {
            int heightOneNumber = getHeightOneNumber(data[i]);
            //如果为1或4直接就是false（定义）
            if (heightOneNumber == 1 || heightOneNumber > MAX_BIT_NUMBER) {
                return false;
            }
            //开始check后面cnt个字节是否为开头是否为10，这里是长度不足heightOneNumber个
            if (i + heightOneNumber - 1 >= n) {
                return false;
            }
            for (int k = i + 1; k < i + heightOneNumber; k++) {
                //check 10
                if ((((data[k] >> HEIGHT_NUMBER) & 1) == 1) && (((data[k] >> (HEIGHT_NUMBER - 1)) & 1) == 0)) {
                    continue;
                }
                return false;
            }
            //以此类推
            if (heightOneNumber == 0) {
                ++i;
            } else {
                i += heightOneNumber;
            }
        }

        return true;
    }

    private int getHeightOneNumber(int current) {
        int j = HEIGHT_NUMBER;
        //计算从第8位往下有多少个1
        while (j >= 0 && (((current >> j) & 1) == 1)) {
            j--;
        }

        return HEIGHT_NUMBER - j;
    }

}
